package Midium;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

// 740.删除并获得点数
/*
 * 结论：贪心是不可行的，假设nums==[1,2,3,4]
 * 按照贪心，首先选择1，然后选择4，则ans=5
 * 但真正的答案应该是首先选择2，然后选择4
 * */
public class Solution740 {

    public static int deleteAndEarn(int[] nums) {
        // 找到nums里最大的数
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(nums[i], max);
        }
        max++;
        int arr[] = new int[max];
        for (int i = 0; i < nums.length; i++) {
            arr[nums[i]]++;
        }
        // arr相当于错误解法里的hasmap的作用
        int[] dp = new int[max];
        dp[0] = 0;
        dp[1] = 1 * arr[1];
        // dp[i]表示，当选择的数字小于等于i的时候，所能获得的最大点数
        // 对于每个数，可以选择用这个数，也可以选择不用这个数，从这二者中选择一个最大的值作为贪心最优情况
        for(int i = 2; i < max ;i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+i*arr[i]);
        }
        return dp[max-1];
    }

    public static int deleteAndEarn_error(int[] nums) {
        int ans = 0; // 用于返回的最大点数(累积基于贪心时，当前已经积累的点数)
        Set<Integer> set = new HashSet<Integer>(); // 用于存放当前有哪些数还可以选
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.replace(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
                set.add(nums[i]);
            }
        }
        // 贪心，每次选择一个数，使得受此影响而删除的数之和是最小的，于是决定选择这个数
        while (!set.isEmpty()) {
            // 遍历所有可以选择的情况，选一个最优解
            int theBestNum = 0;
            int curMin = Integer.MAX_VALUE;
            for (Integer integer : set) {
                int curSum = 0;
                if (map.containsKey(integer - 1)) {
                    curSum += map.get(integer - 1) * (integer - 1);
                }
                if (map.containsKey(integer + 1)) {
                    curSum += map.get(integer + 1) * (integer + 1);
                }
                if (curSum < curMin) {
                    theBestNum = integer;
                    curMin = curSum;
                }
            }
            // 更新map和set
            map.remove(theBestNum + 1);
            map.remove(theBestNum - 1);
            set.remove(theBestNum + 1);
            set.remove(theBestNum - 1);
            if (map.get(theBestNum) == 1) {
                map.remove(theBestNum);
                set.remove(theBestNum);
            } else
                map.replace(theBestNum, map.get(theBestNum) - 1);
            ans += theBestNum;
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(deleteAndEarn(new int[]{1, 2, 3, 4}));
    }
}
